Image information (such as digital video information) is often transmitted from one electronic device to another. Such information is typically encoded and/or compressed to reduce the bandwidth required for transmission and/or to decrease the time necessary for transmission. In some configurations, information about differences between a current picture and a previous picture might be transmitted and the device receiving the image information may then, for example, decode and/or decompress the information (e.g., by using the previous picture and the differences to generate the current picture) and provide the image to a viewing device.
As represented by a block diagram of a system 100 as shown in FIG. 1, for example, an image data frame source 110 may be coupled to provide image data frames to an encoder 120. The encoder 120 may, according to some configurations, apply an encoding and/or compression algorithm in accordance with the Moving Pictures Expert Group (MPEG) Release Two (MPEG-2) 13818 standard (1994) published by the International Standards Organization (ISO) and the International Electrotechnical Commission (IEC), and/or in accordance with the MPEG-4 14496 (1999/2002) standard published by ISO/IEC. The encoder 120 may, for example, utilize motion compensation procedures to allow image frames to be constructed based on previous (and/or future) frames. The encoded and/or compressed information may then be sent to a display device 150. The display device 150 may comprise, for example, a decoder (not separately shown) that may decode and/or decompress the image information for display via the display device 150.
Referring to FIG. 2, a block diagram of an encoder 220 is shown. The encoder 220 may, for example, be similar in configuration and/or functionality to the encoder 120 described in conjunction with FIG. 1. In some configurations, the encoder 220 may include a processor 222, a random access memory (RAM) 224, and/or a cache 226. The processor 222 may, for example, load information associated with reference image frames from the RAM 224 and/or into the cache 226. The reference frame information may then be compared to information from a current frame to estimate motion in the image sequence. One of the most common and effective ways to estimate motion is accomplished using a block-matching algorithm (BMA). A current image frame may, for example, be segmented into blocks of image pixels having pixel dimensions of N×N. Block sizes of 4×4, 4×8, 8×4, 8×8, 8×16, 16×8, and 16×16 (commonly referred to as a “macroblock”) may typically be used.
For each block of the current image, the block is compared to the reference frame to determine the most likely location of the block in the reference frame. To reduce computational overhead, a search window within the reference frame is often identified and the block is compared to various positions within the search window. The search window may, for example, comprise dimensions of (2W+N)×(2W+N), where W is a maximum assumed and/or allowable displacement of the block between frames. The most effective yet computationally intensive way of comparing the block to the search window is to compare the pixels of the block to the pixels of the search window at every position that the block may be moved to within the search window. This is referred to as a “full” or “exhaustive” search. For each position of the block tested within the search window, each pixel of the block is compared to a corresponding pixel in the search window. The comparison comprises computing a deviation between the values of compared pixels.
Often the mathematical sum of absolute differences (SAD), mean squared error (MSE), mean absolute error (MSE), or mean absolute difference (MAD) functions are utilized to quantitatively compare the pixels. The deviations for each block position are then accumulated, and the position within the search window that yields the smallest deviation is selected as the most likely position of the block in the previous frame. The differences in the current and previous positions of the block are then utilized to derive a motion vector to estimate the movement associated with the block between the reference frame and the current frame. The motion vector may then, for example, be transmitted as image information (e.g., instead of a full image frame) so that a decoder may render, recreate, or build the current frame by simply applying the motion vector information to the reference frame.
Even when an exhaustive search is not performed (e.g., various “fast” search algorithms have been proposed and/or used), however, the motion estimation process may often be the most memory-intensive component of image transmission. For every block comparison and/or for every block position in the reference frame search window, for example, the processor 222 may need to load the reference frame information into the cache 226. When upwards of one billion operations are performed per second, this memory traffic may be the limiting factor in image transmission performance and may otherwise be highly undesirable.